#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 *给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

 

示例1：



输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：

输入: root = [1,2,3]
输出: [1,3]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

vector<int> largestValues(TreeNode *root) {
    vector<int> ret;

    queue<TreeNode *> q;
    if (!root)
        return ret;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        int lage = q.front()->val;
        for (int i = 0; i < size; ++i) {
            TreeNode *temp = q.front();
            q.pop();

            if (temp->val > lage)
                lage = temp->val;

            if (temp->left)
                q.push(temp->left);

            if (temp->right)
                q.push(temp->right);
        }
        //这边也可以直接sum 不用容器
        ret.push_back(lage);
    }

    return ret;
}